package algorithm.niuke;

class 自由之路 {
    boolean log = true;

    public int findRotateSteps(String ring, String key) {
        int ringLen = ring.length();
        int keyLen = key.length();
        Integer[][][] map = new Integer[keyLen + 5][ringLen + 5][26];
        int[][] pos = new int[ringLen][26];
        char[] ringChs = ring.toCharArray();
        char[] keyChs = key.toCharArray();
        for (int i = 0; i < ringLen; i++) {
            int ch = ringChs[i];
            int chI = ch - 'a';
            pos[i][chI] = 1;
            map[0][i][chI] = Math.min(i, ringLen - i) + 1;
        }
        char pre = keyChs[0];
        for (int k = 1; k < keyLen; k++) {
            char cur = keyChs[k];
            int preI = pre - 'a';
            int curI = cur - 'a';
            for (int i = 0; i < ringLen; i++) {
                for (int j = 0; j < ringLen; j++) {
                    if (map[k - 1][i][preI] != null && pos[j][curI] == 1) {
                        int dis = Math.abs(i - j);
                        int minDis = map[k - 1][i][preI] + Math.min(dis, ringLen - dis) + 1;
                        if (map[k][j][curI] != null) {
                            minDis = Math.min(map[k][j][curI], minDis);
                        }
                        map[k][j][curI] = minDis;
                        if (log) {
                            System.out.println(pre + "->" + cur + " " + map[k][j][curI]);
                        }
                    }
                }
            }
            pre = cur;
        }
        char end = keyChs[keyLen - 1];
        int endI = end - 'a';
        int min = 1 << 30;
        if (log) {
            System.out.println("end is " + end);
        }
        for (int i = 0; i < ringLen; i++) {
            if (map[keyLen - 1][i][endI] != null) {
                min = Math.min(min, map[keyLen - 1][i][endI]);
            }
        }
        return min;
    }

    public static void main(String[] args) {
        自由之路 run = new 自由之路();
        run.findRotateSteps("edcba", "abc");
    }
}